// Copyright 2010 Keir Mierle. All rights reserved.
//
// A simple implementation of depth-first proof-number search.  The code is
// roughly based on descriptions and pseudo code taken from Akihiro's Ph.D.
// thesis:
//
//   A. Kishimoto. Correct and Efficient Search Algorithms in the Presence of
//   Repetitions. PhD thesis, University of Alberta, 2005.
//
//   http://www.is.titech.ac.jp/~kishi//pdf_file/kishi_phd_thesis.pdf
//
// In particular, see pdf page 38 (document page 22). The general depth-first
// proof-number search algorithm is described in:
//
//   Ayumu Nagai (2002). Df-pn Algorithm for Searching AND/OR Trees and its
//   Applications, Ph.D. Thesis, Department of Computing Science, University of
//   Tokyo.
//
// which is not available online. The trick found below, marked by "1 +
// epsilon", which gives a 40% speedup in my test problems, was taken from:
//
//   J. Pawlewicz, L. Lew (2007). Improving Depth-First PN-Search: 1 + epsilon
//   Trick. LNCS No.4630 pp 160-171 Springer-Verlag,Germany
//
//   http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf
//
// Several important parts are not implemented yet: 
//
// - Issues related to the GHI problem ("Graph History Interaction")
//   http://wiki.cs.pdx.edu/wurzburg2009/nfp/campbell-ghi.pdf
// - Kawano's simulation which is useful for reducing searches of similar
//   positions.
// - Any sort of I/O; at the moment the only output from the algorithm is win
//   or loss (draw is a loss at the moment).
// - Most importantly, Fuego integration.
//
// Other papers to look at:
// http://www.math-info.univ-paris5.fr/~bouzy/publications/kloetzerCIG08-paper.pdf
// http://www.springerlink.com/index/v47864x734410148.pdf ("WPNS")
//

#include <vector>
#include <iostream> 
#include <limits>

#include "using.h"
#include "tt.h"
#include "inttypes.h"
 
struct Threshold {
  int phi, delta;
};

const int kInf = numeric_limits<int>::max();

template<typename Node>
struct DepthFirstProofNumberSearch {
  DepthFirstProofNumberSearch() : tt(2 * 1024 * 1024) {}

  typedef typename Node::Move Move;

  bool BestMove(const Node &node, Move *move) {
    // TODO(keir): Implement this!
    return true;
  }

  bool Explore(const Node &node, uint64 *explored) {
    Threshold threshold;
    threshold.phi = kInf;
    threshold.delta = kInf;

    depth = 0;
    max_depth = 0;
    mid_calls = 0;

    *explored = MultipleIterativeDeepening(node, &threshold);

    int num_filled_entries = 0;
    for (int i = 0; i < tt.table.size(); ++i) {
      if (tt.table[i].key != 0) {
        num_filled_entries++;
      }
    }
    cout << "Occupied tt entries: " << num_filled_entries
         << " out of " << tt.table.size() << "\n";
    cout << "Maximum depth: " << max_depth << "\n";
    cout << "MID calls: " << mid_calls << "\n";
    return threshold.delta == kInf;
  }

  bool Lookup(const Node &node, Threshold *threshold, uint64 *score = NULL) {
    Threshold *found_entry = tt.Lookup(node.Hash(), score);
    if (found_entry) {
      *threshold = *found_entry;
    } else {
      // TODO(keir): If the node offers a method "shortest possible number of
      // moves to a terminal state", that should be called and used instead of
      // 1 here. For example, if it takes 2 moves to complete 2 eyes, then it
      // should be 2. If it is going to take 10 to make 2 eyes, it should be
      // 10. This can increase the speed by avoiding underestimating the
      // difficulty of searching a node.
      threshold->phi = 1;
      threshold->delta = 1;
    }
    return found_entry;
  }

  // Compute the various child-dependent stats in one pass over the children.
  // This saves multiple trips to the transposition table. In particular, this
  // computes 
  //
  //  - The new best child ("SelectChild" in Figure 2.4 of Kishimoto's thesis).
  //  - The node's new "proof""disproof" numbers, which correspond to
  //    delta_min and phi_sum depending on whether the node is a AND or OR
  //    node. These are the PhiSum and DeltaMin methods in Figure 2.4 of
  //    Kishimoto's thesis.
  //
  int ComputeChildInfo(const Node &node,
                       const vector<typename Node::Move> &moves,
                       int *delta_min,
                       int *phi_sum,
                       Threshold *best_child_threshold = NULL,
                       int *phi_for_child_with_smallest_delta = NULL,
                       int *delta_for_child_with_second_smallest_delta = NULL) {
    bool use_wpns = false;
    
    // For select-child
    int best_child = -1;
    int delta_for_child_with_smallest_delta = kInf;
    bool found_best = false;
    if (best_child_threshold) {
      *phi_for_child_with_smallest_delta = kInf;
    }

    // For delta-min
    *delta_min = kInf;

    // For phi-sum
    *phi_sum = 0;

    // Make one pass over the children.
    for (int i = 0; i < moves.size(); ++i) {
      Threshold child_threshold;

      Node child_node = node;
      child_node.MakeMove(moves[i]);

      // Have we visited the child already?
      Lookup(child_node, &child_threshold);

      // For select-child
      if (best_child_threshold && !found_best) {
        if (child_threshold.delta < delta_for_child_with_smallest_delta) {
          best_child = i;

          *best_child_threshold = child_threshold;

          *delta_for_child_with_second_smallest_delta =
            delta_for_child_with_smallest_delta;

          *phi_for_child_with_smallest_delta = child_threshold.phi;
          delta_for_child_with_smallest_delta = child_threshold.delta;

        } else if (child_threshold.delta <
                   *delta_for_child_with_second_smallest_delta) {
          *delta_for_child_with_second_smallest_delta = child_threshold.delta;
        }
        if (child_threshold.phi == kInf) {
          found_best = true;
        }
      }

      // For delta-min
      *delta_min = min(*delta_min, child_threshold.delta);

      // For phi-sum.
      if (!use_wpns /* normal df-pn */) {
        //
        // This is trickier than straight addition, because the "infinites" are
        // integers with maximum value, so adding anything to them causes
        // overflow. The below code enforces that x + inf == inf.
        if (child_threshold.phi != kInf && *phi_sum != kInf) {
          *phi_sum += child_threshold.phi;
        } else {
          // One of phi_sum or the child phi was inf, so the result is inf.
          *phi_sum = kInf;
        }
      } else {
        // "df-wpns" from [4]. See page 162. Currently this doesn't work, and
        // it is not clear why.
        if (child_threshold.phi == 0) {
          *phi_sum += 1;
        } else {
          *phi_sum = max(*phi_sum, child_threshold.phi);
        }
      }
    }
    return best_child;
  }
                                                                       
  // Returns number of newly expanded nodes.
  uint64 MultipleIterativeDeepening(const Node &node,
                                    Threshold *parent_threshold) {
    mid_calls++;
    depth++;
    max_depth = max(depth, max_depth);

#if 0
    cout << "At node with thresholds " << parent_threshold->phi
         << ", " << parent_threshold->delta 
         << " and depth " << depth 
         << " and mid calls " << mid_calls << "\n";
    node.Debug();
#endif

    uint64 previously_explored = 1;
    Threshold node_threshold;
    Lookup(node, &node_threshold, &previously_explored);

    if (parent_threshold->phi   <= node_threshold.phi ||
        parent_threshold->delta <= node_threshold.delta) {
      *parent_threshold = node_threshold;
      depth--;
      return 1;
    }

    if (node.IsTerminal()) {
      if (!node.IsWin()) {
        parent_threshold->phi = kInf;
        parent_threshold->delta = 0;
      } else {
        parent_threshold->phi = 0;
        parent_threshold->delta = kInf;
      }
      tt.Store(node.Hash(), *parent_threshold, 1);
      depth--;
      return 1;
    }

    vector<typename Node::Move> moves;
    node.GenerateMoves(&moves);

    // Store the current node in the transposition table to avoid cycling.
    assert(parent_threshold->phi >= 0);
    assert(parent_threshold->delta >= 0);
    tt.Store(node.Hash(), *parent_threshold, previously_explored);

    // Count 1 for this interior node.
    uint64 newly_explored = 1;

    // Explore the children until the threshold for this node is learger than
    // any of the children, which implies that the most proving node is
    // elsewhree (i.e. in a sibling of this node).
    while (true) {
      int delta_min, phi_sum;
      int phi_for_child_with_smallest_delta;
      int delta_for_child_with_second_smallest_delta;
      Threshold best_child_threshold;
      int best_child =
        ComputeChildInfo(node,
                         moves,
                         &delta_min,
                         &phi_sum,
                         &best_child_threshold,
                         &phi_for_child_with_smallest_delta,
                         &delta_for_child_with_second_smallest_delta);

      if (!(parent_threshold->phi > delta_min &&
            parent_threshold->delta > phi_sum)) {
        break;
      }

      best_child_threshold.phi =
        // Use max to properly handle infinities by detecting wraparound.
        max(parent_threshold->delta +
            phi_for_child_with_smallest_delta -
            phi_sum,
            0);

      best_child_threshold.delta =
        min(parent_threshold->phi,
            // Use max to properly handle infinities by detecting wraparound.
            max(delta_for_child_with_second_smallest_delta +
                 // (1 + eps) trick with eps = 1/4.
                (delta_for_child_with_second_smallest_delta + 3) / 4,
                 delta_for_child_with_second_smallest_delta));

      Node child_node = node;
      child_node.MakeMove(moves[best_child]);

      newly_explored +=
        MultipleIterativeDeepening(child_node, &best_child_threshold);
    }

    int delta_min, phi_sum;
    ComputeChildInfo(node, moves, &delta_min, &phi_sum);
    parent_threshold->phi = delta_min;
    parent_threshold->delta = phi_sum;
    assert(parent_threshold->phi >= 0);
    assert(parent_threshold->delta >= 0);
    tt.Store(node.Hash(),
             *parent_threshold,
             // Store the total visits to this node & children, but return only
             // the number of newly explored nodes. This avoids double counting.
             previously_explored + newly_explored);

    depth--;
    return newly_explored;
  }

  TranspositionTable<uint64, Threshold> tt;
  int depth;
  int max_depth;
  int mid_calls;
};

template<typename Node>
bool DFPNS(const Node &node, uint64 *explored) {
  DepthFirstProofNumberSearch<Node> dfpns;
  return dfpns.Explore(node, explored);
}

